# 插入排序思想:就像打牌时整理牌，小的插到左边，大的插到右边
# 算法特点:最坏情况下时间复杂度O(N^2)
# 依赖于初始排列顺序，特别适合于部分有序的数组
# 完全有序的情况下,复杂度能达到O(N),但逆序时效率降到O(N^2)
# [12, 5, 6, 3, 9]
def insertion_sort(nums):
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1 # 跟前一个值去比
        # print(i, 'insertion sort', j, 'key=', key)
        # 将key 插入到前面已经排好序的序列中
        # j: 0 1 2 3
        print(f'第{i}轮, {key}')
        # 这里跟输出 9*9乘法表很像
        while j >= 0 and key < nums[j]:
            print('nums[j]', nums[j])
            nums[j + 1] = nums[j] # nums[i] = nums[j]
            j -= 1 # 退出循环 → 在位置0插入2 → [2, 5, 4, 6, 1, 3]  # 在前1个位置
            # 相当于  j-- 3 2 1 0
            nums[j + 1] = key
        print(f'第{i}轮------end')
    return nums


if __name__ == '__main__':
    # nums = [5, 4, 3, 2, 1]
    # nums = [12, 5, 6, 3, 9]
    nums = [5, 4, 3, 2, 1]
    print(insertion_sort(nums))


"""
示例演示
假设我们要排序数组：[5, 2, 4, 6, 1, 3]

第1轮（i=1，key=2）：

比较：2 < 5 → 将5右移 → 数组变为[5, 5, 4, 6, 1, 3]

j=-1，退出循环 → 在位置0插入2 → [2, 5, 4, 6, 1, 3]

第2轮（i=2，key=4）：

比较：4 < 5 → 将5右移 → [2, 5, 5, 6, 1, 3]

比较：4 > 2 → 退出循环 → 在位置1插入4 → [2, 4, 5, 6, 1, 3]

继续这个过程，直到所有元素都排序完成。



在前一个位置插入， 索引 - 1 呗

在后一个位置插入  索引 + 1 呗
"""
